"""
2917. 找出数组中的 K-or 值
简单
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K-or 操作。在 K-or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值是 1 。

返回 nums 的 K-or 值。



示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
用二进制表示 numbers：
Number	Bit 3	Bit 2	Bit 1	Bit 0
7	0	1	1	1
12	1	1	0	0
9	1	0	0	1
8	1	0	0	0
9	1	0	0	1
15	1	1	1	1
Result = 9	1	0	0	1
位 0 在 7, 9, 9, 15 中为 1。位 3 在 12, 9, 8, 9, 15 中为 1。 只有位 0 和 3 满足。结果是 (1001)2 = 9。
示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：没有位在所有 6 个数字中都为 1，如 k = 6 所需要的。所以，答案为 0。
示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。


提示：

1 <= nums.length <= 50
0 <= nums[i] < 231
1 <= k <= nums.length
"""
from typing import List


class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        dp = [0] * 32
        for num in nums:
            i = 0
            while num != 0:
                if num & 1 == 1:
                    dp[i] += 1
                i += 1
                num = num >> 1
        print(dp)
        ans = 0
        #i是位，j是次数
        for i,j in enumerate(dp):
            if j>=k:
                #如果1数量>=k,则当前位数的1是有效的
                ans = ans | (1 << i)
        return ans
    def findKOr_res1(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(max(nums).bit_length()):
            cnt1 = sum(x >> i & 1 for x in nums)
            if cnt1 >= k:
                ans |= 1 << i
        return ans

if __name__ == '__main__':
    print(Solution().findKOr([7,12,9,8,9,15],4))

